\documentclass[a4paper,12pt]{report}

\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{multicol}

\title{Programmation fonctionelle}
\author{Université de Strasbourg}
\date{D'après le cours de M. \'Eric Violard}

\pagestyle{headings}

\begin{document}

\maketitle
\tableofcontents

\chapter{Introduction}
\section{Modèle}
Chaque langage de programmation est basé sur un mode de programmation fondamental :
\begin{itemize}
\item[\textbullet]{impératif,}
\item[\textbullet]{fonctionnel,}
\item[\textbullet]{logique.}
\end{itemize}
Chacun de ces modes est basé sur un modèle mathématique pour exprimer la relation entre données et résultats.

\subsection{Mode logique}
La relation est donnée par une formule logique. Le programme est une formule logique, consitituée de connecteurs logiques. Par 
exemple :
\begin{verbatim}
max(A,B,M) :- A>=B, M=A.
max(A,B,M) :- B>=A, M=B.
\end{verbatim}
L'éxecution d'un programme en mode logique consiste en fait à construire la preuve logique.

Exemple d'exécution :
\begin{verbatim}
|?- max(2,7,17).
     2>=7 ?    Fail
     7>=2 ?
     M=7
\end{verbatim}

\subsection{Mode fonctionel}
La relation est restreinte à une fonction. Le programme est composé d'une ou plusieurs fonctions. Par exemple,
\begin{verbatim}
let max(a,b) = if a>=b then a else b;;
\end{verbatim}
L'exécution correspond donc à l'application de la fonction.

Exemple d'exécution :
\begin{verbatim}
# max(2,7);;
   if 2>=7 then 2 else 7
 = if false then 2 else 7
 = 7
\end{verbatim}

\subsection{Mode impératif}
C'est un mode atypique et plus complexe. Ici, on modélise des états mémoires. Le programme n'est qu'une fonction de transition d'un
état mémoire initial vers un état mémoire final. C'est une séquence d'affectations. Par exemple,
\begin{verbatim}
m=a;
if(b>)a) m=b;
return m;
\end{verbatim}
L'exécution correspond à une succession de transitions.

Exemple d'exécution :\\
\begin{center}
\begin{tabular}{| c | c | c | c |} \hline
\'Etat mémoire & \'Etat initial & Transition & \'Etat final \\ \hline \hline
a & 2 & 2 & 2 \\ \hline
b & 7 & 7 & 7 \\ \hline
m & -- & 2 & 7 \\ \hline
\end{tabular}
\end{center}

\vspace{10pt}

Tous ces modes de programmation utilisent des variables, mais le sens du mot \textit{variable} diffère.

\vspace{10pt}

En programmation fonctionnelle et logique : une variable a le même sens qu'en mathématiques, qu'un inconnue dans une équation. Résoudre l'équation en donne une définition explicite

\vspace{10pt}

En programmation impérative, une variable est l'expression abstraite d'une adresse en mémoire. Une définition est appellée "affectation" et signifie le rangement d'une valeur à cette adresse.

\section{Propriété de transparence référentielle}
\begin{quotation}\textit{"Le résultat d'un programme ne change pas si on remplace une expression par une autre expression de valeur égale"}\end{quotation}

Cette citation est vraie en programmation fonctionnelle ou en logique, mais elle est fausse en programmation impérative. C'est d'ailleurs à l'origine de nombreuses difficultés de programmation.
Exemple : substitution de $a$ par $x$ définition dans ce programmation impératif :
\begin{verbatim}
a=b+1;
b=a;
return a;
\end{verbatim}

\subsection{\'Elément impur}
Un élément d'un langage est dit \textit{impur} s'il contredit d'une manière ou d'une autre la propriété de transparence référentielle (ici, l'affectation).

Quelques langages pour chacun des modes de programmation :
\begin{itemize}
\item[\textbullet]{impératif (\url{C,PASCAL,FORTRAN}),}
\item[\textbullet]{fonctionnel (\url{ML,HASKELL,MIRANDA,LISP}),}
\item[\textbullet]{logique (\url{PROLOG}).}
\end{itemize}

\paragraph{}
Le langage support de ce cours sera l'Objective Caml (\url{OCaml}), débarrassé de ses éléments impurs : l'affectation, l'utilisation des variables au sens impératif, pointeurs, tableaux...).

\section{Comparaison du mode fonctionnel avec le mode impératif}
La programmation fonctionnelle présente certains avantages par rapport à la programmation impérative.
\subsection{Avantages}
\subsubsection{Puissance d'expression:}
Par rapport au mode impératif, le mode fonctionnel est beaucoup plus concis. Il permet également d'utiliser facilement les types algébriques, plus facilement qu'avec un langage de de programmation impératif.
\subsubsection{Facilité de programmation:}
La plupart des langages de programmation fonctionnels présentent des contrôleurs de types et une gestion de la mémoire laissée au compilateur, ce qui permet d'éviter les fuites de mémoires.
\subsection{Inconvénients}
Le code exécutable provenant d'un langage de programmation fonctionnel possède une efficacité moindre par rapport à un code exécutable provenant d'un langage de programmation impératif. Néanmoins, les performances moyennes sont comparables.

\chapter{Programmer avec des fonctions}

En mathématiques, une fonction $f$ fait correspondre à chaque élément d'un ensemble $A$ (appellé \textit{domaine} de la fonction), un élément unique d'un autre ensemble $B$ (appellé \textit{codomaine} de la fonction). On note : \[f : A \rightarrow B\]

Exemple : la fonction qui à tout entier associe son suivant : il y a plusieurs manières de définir de telles fonctions.

Une manière élégante consiste à utiliser une équation, ou \textit{règle de correspondance}, d'un élément du domaine vers un élément du codomaine. Par exemple, \[f(x)=x+1\]où
\begin{itemize}
\item[\textbullet]{$f$ est le nom de la fonction}
\item[\textbullet]{$f(x)$ l'image de $x$ par $f$}
\item[\textbullet]{$x$ est un paramètre formel qui désigne un élément du domaine de la fonction}
\end{itemize}
En \url{OCaml}, on aurait :
\begin{verbatim}let f(x) = x+1;;\end{verbatim}
Exécution du programme :\begin{itemize}
\item[\textbullet]{avec l'interpréteur (exécution interactive) \\
\begin{verbatim}
# let f(x) = x+1;;
  val f = int -> int = <fun>
# f(1);;
  -:int = 2
\end{verbatim}}
\item[\textbullet]{avec le compilateur : il est nécessaire de réaliser les E/S. Pour cela, on utilise des fonctions prédéfinies.
\vspace{10pt}
\begin{verbatim}
let f(x) = x+1;;
print_int(f(read_int()));;
\end{verbatim}
\vspace{10pt}
Ensuite, via un terminal :
\vspace{10pt}
\begin{verbatim}
$ ocamlc suivant.ml
$ ./a.out
  1
  2
\end{verbatim}}
\end{itemize}
Une fonction complexe peut être définie comme une composition de fonctions plus simples. En exemple, la fonction qui, à un triplet de nombres associe le plus grand des trois.
\begin{verbatim}
let max3(a,b,c) = max2(a,max2(b,c));;
\end{verbatim}
\begin{itemize}
\item[\textbullet]{Le domaine de cette fonction est l'ensemble des triplets de nombres : on doit voir cette fonction comme une fonction à un seul argument qui serait un triplet}
\item[\textbullet]{On utilise trois paramètres formels a, b et c pour désigner un tel triplet}
\item[\textbullet]{On aurait pu utiliser un seul paramètre x :
\begin{verbatim}let max3(x) = ...\end{verbatim}
mais la définition aurait été plus compliquée, car on aurait eu besoin d'extraire ou de "filtrer" les trois nombres du triplet.}
\end{itemize}
\vspace{10pt}
Pour compléter cette défintion de \url{max3}, il faut définir \url{max2}. En mathématiques, on pourrait écrire :
max2(a,b) = a si a>b, b sinon
en introduisant une décomposition par cas.\\

En \url{OCaml}, on utilise une conditionnelle \url{if...then...else}
\begin{verbatim}let max2(a,b) = if a>=b then a else b;;\end{verbatim}
NB : ce mode de programmation supporte une démarche déductive pour construire un programme.

\section{Quelques facilités en OCaml}
\subsection{Fonctions anonymes}
En mathématiques, on peut utiliser une fonction sans pour autant la nommer. On \url{OCaml}, on peut le faire aussi en itilisant le mot-clef \url{function}.
\begin{verbatim}
# function x -> 2*x+1;;
-: int -> int = <fun>
# (function: x -> 2*x+1)(1);;
-: int 3
\end{verbatim}

\subsection{Définitions temporaires}
En mathématiques, on introduit parfois une variable pour simplifer l'expression du résultat. On \url{OCaml}, on peut le faire également en utilisant la syntaxe \url{let...in...}. Par exemple :
\begin{verbatim}
# let moyenne (a,b) = let somme = a+b in somme/2;;
val moyenne : int*int -> int = <fun>
\end{verbatim}


------------------




ensemble borné par N
\begin{verbatim}
typedef struct strens { Nat v[N]; Nat n; } StrEns, *Ens;              // Tableau statique
typedef struct strens { Nat *v  ; Nat n; Nat taille; } StrEns, *Ens;  // Tableau dynamique
\end{verbatim}
















\chapter*{Références bibliographiques}
\addcontentsline{toc}{chapter}{Références bibliographiques}
\begin{itemize}
\item[\textbullet]{\textit{Functional Programming} \\ Anthony J. Field, Peter G Harrisson}
\item[\textbullet]{\textit{Mise en oeuvre des langages fonctionnels de programmation} \\ Simon L. Peyton Jones}
\item[\textbullet]{\textit{Approche fonctionelle de la programmation} \\ Grey Counneau, Michel Mauny}
\end{itemize}


\end{document}